// 复赛改动：每个卫星有对应的功耗系数

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include "data.h"
#include <ctime>
using namespace std;

//#define DEBUG 1

/****** 类型定义 ******/
// 信号
struct SIGNAL{
    uint32_t id;              // 初始id
    uint32_t power;           // 发射基站的功耗（复赛）
    uint32_t curr;            // 当前信号所在顶点的id
    uint32_t left_dist;       // 剩余距离
    vector<uint32_t> route;   // 路径点集
    vector<uint32_t> edges;   // 路径边集
};
// 顶点
struct VERTEX{
    uint32_t id;
    bool isMiddle;            // 是否一定是中继节点
    set<uint32_t> edges;      // 顶点的邻边
    set<uint32_t> neighbors;  // 顶点的邻点
    set<uint32_t> signals;    // 顶点上的信号
};
// 边
struct EDGE{
    uint32_t id;
    uint32_t v1;              // 顶点1
    uint32_t v2;              // 顶点2
    uint32_t dist;            // 边的长度
    uint32_t color;           // 边的颜色
};
// 子网
struct SubNetwork{
    uint32_t n;               // 节点个数
    set<uint32_t> signals;    // 子网信号集合
    set<uint32_t> edges;      // 子网边集
    set<uint32_t> vertexs;    // 子网点集
    map<uint32_t, SIGNAL> id2signal;
    map<uint32_t, EDGE> id2edge;
    map<uint32_t, VERTEX> id2vertex;
    map<pair<uint32_t, uint32_t>, uint32_t> vertexs2edge;   // 边的两个顶点与边本身的映射
};
// 并查集
class Disjoint_Sets{
public:
    vector<uint32_t> ds_fa, ds_rank;
    void ds_init(uint32_t n){
        for (uint32_t i = 0; i < n; ++i){
            ds_fa.push_back(i);
            ds_rank.push_back(1);
        }
    }
    uint32_t ds_find(uint32_t x) {
        return (x == ds_fa[x]) ? x : (ds_fa[x] = ds_find(ds_fa[x]));
    }
    void ds_union(uint32_t i, uint32_t j) {
        uint32_t x = ds_find(i), y = ds_find(j);
        if (ds_rank[x] <= ds_rank[y]) ds_fa[x] = y;
        else ds_fa[y] = x;
        if (ds_rank[x] == ds_rank[y] && x != y) ds_rank[y]++;
    }
};

/****** 全局常量 ******/
constexpr uint32_t UNDEFINED_NUMBER = 10000000;  // 边未着色的初始状态
constexpr uint32_t EXIT_TIME = 280;              // 退出时间（s）

/****** 全局变量 ******/
clock_t begin_time;
uint32_t gN, gE, gC, gD, gPS;       // 全局参数
vector<bool> id2type;               // 节点id的类型

map<uint32_t, SIGNAL> all_signals;  // 全部信号的集合
vector<VERTEX> all_vertexs;         // 全部顶点的集合
vector<EDGE> all_edges;             // 全部边的集合
vector<SubNetwork> networks;        // 子网网络集合

// 复赛
vector<int> gpower;                  // 顶点的功耗（主要是基站的）

/****** 函数声明 ******/
void parse_data(uint32_t N, uint32_t C, uint32_t D, uint32_t PS,
                const vector<bool>& typeVec, const vector<int>& power,
                const vector<Edge>& edgeVec);
void divide_network(const vector<Edge>& edgeVec);

void transfer_signals(uint32_t nid, uint32_t old_vid, uint32_t new_vid, vector<uint32_t> transfer_route);
uint32_t vertex_left_dist(uint32_t nid, uint32_t vid);
uint32_t vertex_power_rank(uint32_t nid, uint32_t vid);
vector<uint32_t> vid_has_signals(uint32_t nid);

void basic_route(uint32_t nid);

void merge_signals1(uint32_t nid);
bool find_a_route1(uint32_t nid, uint32_t vid, vector<uint32_t>& transfer_route, uint32_t& lowered_cost);
bool dfs1(uint32_t nid, uint32_t curr, uint32_t color, uint32_t curr_distance, uint32_t& min_distance,
          vector<bool> visited, vector<uint32_t> route_curr, vector<uint32_t>& transfer_route);

void merge_signals2(uint32_t nid);
bool find_a_route2(uint32_t nid, uint32_t vid, uint32_t& vid2, vector<uint32_t>& transfer_route1, vector<uint32_t>& transfer_route2, uint32_t& lowered_cost);
bool dfs2(uint32_t nid, uint32_t curr, uint32_t curr_distance, uint32_t& min_distance, uint32_t vid1_leftd,
          vector<bool> visited, vector<uint32_t> route_curr, vector<uint32_t>& route_record);

void merge_signals3(uint32_t nid);


void merge_signals_euro_cup(uint32_t nid);
void paint_vertexs_euro_cup(uint32_t nid, uint32_t vid, uint32_t left_distance, vector<bool>& visited, vector<uint32_t>& vertex_color);
bool dfs_euro_cup(uint32_t nid, uint32_t curr, uint32_t target, uint32_t color, uint32_t curr_distance, uint32_t& min_distance,
                  vector<bool> visited, vector<uint32_t> route_curr, vector<uint32_t>& route_record);

/****** 函数实现 ******/
/* 解析数据 */
void parse_data(uint32_t N, uint32_t C, uint32_t D, uint32_t PS,
                const vector<bool>& typeVec, const vector<int>& power,
                const vector<Edge>& edgeVec){
    gN = N; gE = edgeVec.size(); gC = C; gD = D; gPS = PS; id2type = typeVec; gpower = power;
    // 顶点和信号
    for(uint32_t i = 0; i<gN; ++i){
        VERTEX V;
        V.id = i;
        V.isMiddle = false;
        if(!id2type[i]){    // 同时为顶点和信号节点
            V.signals.insert(i);

            SIGNAL S;
            S.id = i;
            S.power = power[i];
            S.curr = i;
            S.left_dist = gD;
            S.route.push_back(i);
            all_signals.insert({i, S});
        }
        all_vertexs.push_back(V);
    }
    // 边
    for(uint32_t i = 0; i<gE; ++i){
        EDGE E{};
        E.id = i;
        E.v1 = edgeVec[i].send;
        E.v2 = edgeVec[i].recv;
        E.dist = edgeVec[i].dist;
        E.color = UNDEFINED_NUMBER;
        all_edges.push_back(E);

        all_vertexs[E.v1].edges.insert(i);
        all_vertexs[E.v2].edges.insert(i);
        all_vertexs[E.v1].neighbors.insert(E.v2);
        all_vertexs[E.v2].neighbors.insert(E.v1);
    }
}

/* 划分子网 */
void divide_network(const vector<Edge>& edgeVec) {
    // 并查集——初始化、合并查找
    Disjoint_Sets ds;
    ds.ds_init(gN);
    for (auto& edge:edgeVec) ds.ds_union(edge.send, edge.recv);

    vector<uint32_t> v2fa(gN);  // 每个顶点对应的家族编号
    for(uint32_t i=0; i<gN; ++i){
        v2fa[i] = ds.ds_find(i);
    }
    set<uint32_t> unique_fa(v2fa.begin(), v2fa.end());  // 合并后家族唯一编号

    // 构建子网
    for (uint32_t fid:unique_fa) {
        SubNetwork sn;
        uint32_t cnt = 0;
        for(auto& s:all_signals){
            if(v2fa[s.first] == fid){
                sn.signals.insert(s.first);
                sn.id2signal[s.first] = s.second;
            }
        }
        for(auto& v:all_vertexs){
            if(v2fa[v.id] == fid){
                sn.vertexs.insert(v.id);
                sn.id2vertex[v.id] = v;
                cnt++;  // 计数子网顶点个数
            }
        }
        for(auto& e:all_edges){
            if(v2fa[e.v1] == fid && v2fa[e.v2] == fid){
                sn.edges.insert(e.id);
                sn.id2edge[e.id] = e;
                // 构建边的两个顶点到这条边的映射关系
                sn.vertexs2edge.insert({make_pair(e.v1, e.v2), e.id});
                sn.vertexs2edge.insert({make_pair(e.v2, e.v1), e.id});
            }
        }
        sn.n = cnt;
        networks.push_back(sn);
    }
}

/* 信号迁移
 * 将old_vid节点上的全部信号按照transfer_route迁移到new_vid，更新相关结构体
 * */
void transfer_signals(uint32_t nid, uint32_t old_vid, uint32_t new_vid, vector<uint32_t> transfer_route){
    if(transfer_route.size() <= 1) return;

    auto& sub_network = networks[nid];
    auto& old_vertex = sub_network.id2vertex[old_vid];  // 源顶点
    auto& new_vertex = sub_network.id2vertex[new_vid];  // 目的顶点

    uint32_t transfer_route_size = transfer_route.size();
    for(uint32_t sid:old_vertex.signals){
        auto& signal = sub_network.id2signal[sid];
        // 更新信号当前位置
        signal.curr = new_vid;
        // 更新信号路径
        for(uint32_t i=1; i<transfer_route_size; ++i){
            signal.route.push_back(transfer_route[i]);  // 路径点集
            uint32_t eid = sub_network.vertexs2edge[make_pair(transfer_route[i-1], transfer_route[i])];
            signal.edges.push_back(eid);  // 路径边集
            signal.left_dist -= sub_network.id2edge[eid].dist;  // 信号剩余距离
            sub_network.id2vertex[transfer_route[i-1]].isMiddle = true;  // 标记中继卫星
        }
        // 信号经过的边重新着色
        for(uint32_t eid:signal.edges){
            sub_network.id2edge[eid].color = new_vid;
        }
        // 新节点增加信号
        new_vertex.signals.insert(sid);
    }
    old_vertex.signals.clear();     // 原节点删除信号
}

/* 获取顶点上信号剩余的最短距离
 * */
uint32_t vertex_left_dist(uint32_t nid, uint32_t vid){
    auto& sub_network = networks[nid];
    auto& vertex = sub_network.id2vertex[vid];
    if(vertex.signals.empty()) return 0;

    uint32_t left_d = UINT32_MAX;
    for(uint32_t sid:vertex.signals){
        uint32_t s_d = sub_network.id2signal[sid].left_dist;
        left_d = left_d <= s_d ? left_d : s_d;
    }
    return left_d;
}

/* 获取顶点上信号功耗的优先级
 * 数值越大越好
 * */
uint32_t vertex_power_rank(uint32_t nid, uint32_t vid){
    auto& sub_network = networks[nid];
    auto& vertex = sub_network.id2vertex[vid];
    if(vertex.signals.empty()) return 0;
    uint32_t signals_num = vertex.signals.size();

    uint32_t rank = UINT32_MAX;
    uint32_t r_sum = 0;
    for(uint32_t sid:vertex.signals){
        uint32_t p = sub_network.id2signal[sid].power;
        r_sum += p;
    }
    rank = 1 + 90*r_sum/signals_num;        // 优先级函数
    return 100 - rank;
}


/* 获取子网中有信号的顶点的id
 * 按照顶点上的信号剩余距离从大到小排序 并且 考虑信号的发射基站的功耗
 * */
vector<uint32_t> vid_has_signals(uint32_t nid){
    auto& sub_network = networks[nid];
    set<pair<int, uint32_t> > id_dis;
    for(uint32_t vid:sub_network.vertexs){
        auto& vertex = sub_network.id2vertex[vid];
        if(vertex.signals.empty()) continue;    // 顶点上无信号则跳过
        uint32_t left_d = vertex_left_dist(nid, vid);   // 剩余距离
        uint32_t rank = vertex_power_rank(nid, vid);    // 顶点的功耗的优先级
        uint32_t order;
        if(left_d*4 > gD){
            order = left_d + rank*10;
        }else{
            order = left_d + rank*365;
        }
        id_dis.insert({-order, vid});
    }
    vector<uint32_t> ans;
    for(auto &item:id_dis) ans.push_back(item.second);
    return ans;
}

/* 规划从基站到最近卫星的路线
 * 这一步可以得到整个问题的可行解
 * */
void basic_route(uint32_t nid) {
    auto& sub_network = networks[nid];
    for(uint32_t sid:sub_network.signals){
        auto& signal = sub_network.id2signal[sid];
        auto& vertex = sub_network.id2vertex[signal.curr];
        // 获取信号的下一顶点和边（题目保证唯一）
        uint32_t next_v = *(vertex.neighbors.begin());
        uint32_t next_e = *(vertex.edges.begin());
        // 更改信号走过的边的属性
        auto& edge = sub_network.id2edge[next_e];
        edge.color = next_v;
        // 更改信号当前位置和走过的路径
        signal.curr = next_v;
        signal.left_dist -= edge.dist;
        signal.route.push_back(next_v);
        signal.edges.push_back(next_e);
        // 原顶点删除信号
        vertex.signals.clear();
        // 新顶点加入信号
        sub_network.id2vertex[next_v].signals.insert(sid);
    }
}

/* 合并子网中的信号
 * 在basic_route的基础上，满足约束条件进行合并
 * 进一步减小功耗成本，其中每次合并都在可行的状态之间转移
 * 合并的最终顶点只会是两个待合并的顶点其中一个，不会合并到第三个空白顶点
 * */
void merge_signals1(uint32_t nid){
    auto& sub_network = networks[nid];

    // 取出有信号的顶点，按照信号剩余最短距离排序 && 按照发射基站的功耗排序
    vector<uint32_t> id_dis = vid_has_signals(nid);

    for(uint32_t vid:id_dis){
        auto& vertex = sub_network.id2vertex[vid];
        if(vertex.signals.empty()) continue;    // 顶点上无信号则跳过

        // 寻找可行的转移路径
        vector<uint32_t> transfer_route;
        uint32_t lowered_cost;
        bool f = find_a_route1(nid, vid, transfer_route, lowered_cost);

        // 进行信号转移
        if(f){
            transfer_signals(nid, vid, transfer_route.back(), transfer_route);
        }
    }
}

/* 找一条最近的合并的路线，让本节点的信号能进行合并
 * */
bool find_a_route1(uint32_t nid, uint32_t vid, vector<uint32_t>& transfer_route, uint32_t& lowered_cost){
    auto& sub_network = networks[nid];
    auto& vertex = sub_network.id2vertex[vid];

    uint32_t left_d = vertex_left_dist(nid, vid);
    vector<bool> visited(gN, false);
    vector<uint32_t> route_curr;
    route_curr.push_back(vid);
    bool f = dfs1(nid, vid, UNDEFINED_NUMBER, 0, left_d, visited, route_curr, transfer_route);
    if(f){
        // 计算路途增加的花费
        uint32_t path_add_cost = 0;
        for(uint32_t i=1; i<transfer_route.size(); ++i){
            uint32_t eid = sub_network.vertexs2edge[make_pair(transfer_route[i-1], transfer_route[i])];
            for(uint32_t sid : vertex.signals){
                path_add_cost += sub_network.id2edge[eid].dist*sub_network.id2signal[sid].power;
            }
        }

        // 计算总共节省的花费
        lowered_cost = gPS - path_add_cost*gC;
        if(lowered_cost > 0) return true;  // 路径增加的花费小于减少的接收卫星的花费时，寻路成功
    }
    return false;
}

bool dfs1(uint32_t nid, uint32_t curr, uint32_t color, uint32_t curr_distance, uint32_t& min_distance,
          vector<bool> visited, vector<uint32_t> route_curr, vector<uint32_t>& transfer_route){
    if(visited[curr] || curr_distance >  min_distance) return false;

    visited[curr] = true;  // 标记顶点已遍历

    auto& sub_network = networks[nid];
    auto& vertex = sub_network.id2vertex[curr];
    if(!vertex.signals.empty() && curr_distance > 0){   // 找到邻近的有信号顶点
        min_distance = curr_distance;
        transfer_route = route_curr;
        return true;
    }

    bool f = false;
    for(uint32_t vid:vertex.neighbors){
        // 信号不能再回发射基站
        if(!id2type[vid]) continue;
        uint32_t eid = sub_network.vertexs2edge[make_pair(curr, vid)];
        auto& edge = sub_network.id2edge[eid];
        // 路径长度限制
        if(curr_distance + edge.dist > min_distance) continue;
        // 路径重合约束
        if(edge.color != UNDEFINED_NUMBER && color != UNDEFINED_NUMBER){
            if(color != edge.color) continue;
        }else if(edge.color != UNDEFINED_NUMBER && color == UNDEFINED_NUMBER){
            color = edge.color;
        }else if(edge.color == UNDEFINED_NUMBER && color != UNDEFINED_NUMBER){
            continue;
        }

        route_curr.push_back(vid);  // 做出选择
        f |= dfs1(nid, vid, color, curr_distance + edge.dist, min_distance, visited, route_curr, transfer_route);
        route_curr.pop_back();  // 撤销选择
    }
    return f;
}

/* 合并信号2
 * 区别于merge_signals1,本合并信号将信号合并在第三个空白顶点上
 * */
void merge_signals2(uint32_t nid){
    auto& sub_network = networks[nid];

    // 取出有信号的顶点，按照信号剩余最短距离排序
    vector<uint32_t> id_dis = vid_has_signals(nid);

    for(uint32_t vid:id_dis){
        auto& vertex = sub_network.id2vertex[vid];
        if(vertex.signals.empty()) continue;    // 顶点上无信号则跳过

        // 寻找可行的转移路径
        uint32_t vid2 = UNDEFINED_NUMBER;
        vector<uint32_t> transfer_route1, transfer_route2;
        uint32_t lowered_cost;
        bool f = find_a_route2(nid, vid, vid2, transfer_route1, transfer_route2, lowered_cost);

        // 如果找到转移路径，则进行信号转移
        if(f){
            transfer_signals(nid, vid, transfer_route1.back(), transfer_route1);
            transfer_signals(nid, vid2, transfer_route2.back(), transfer_route2);
        }
    }
}


bool find_a_route2(uint32_t nid, uint32_t vid, uint32_t& vid2, vector<uint32_t>& transfer_route1, vector<uint32_t>& transfer_route2, uint32_t& lowered_cost){
    auto& sub_network = networks[nid];
    auto& vertex = sub_network.id2vertex[vid];

    // 取出该顶点上剩余路径最短信号的路径长度
    uint32_t left_d = vertex_left_dist(nid, vid);

    uint32_t min_distance = left_d+gD;
    vector<bool> visited(gN, false);
    vector<uint32_t> route_curr, transfer_route;
    route_curr.push_back(vid);
    bool f = dfs2(nid, vid, 0, min_distance, left_d, visited, route_curr, transfer_route);
    if(f){
        vid2 = transfer_route.back();
        auto& vertex2 = sub_network.id2vertex[vid2];
        uint32_t left_d2 = vertex_left_dist(nid, vid2);

        // 找到路径上可以合并的顶点
        uint32_t distance_sum = min_distance;  // 路程总长度
        int s1 = vertex.signals.size(), s2 = vertex2.signals.size();
        uint32_t min_cost = UINT32_MAX;
        uint32_t merged_vid = UNDEFINED_NUMBER;
        if(distance_sum <= left_d2){  // 将vid2的信号合并到vid顶点
            min_cost = distance_sum*s2;
            merged_vid = transfer_route[0];
        }

        uint32_t dis1 = 0;
        for(uint32_t i=1; i<transfer_route.size(); ++i){  // 合并到路途中间的点
            uint32_t eid = sub_network.vertexs2edge[make_pair(transfer_route[i-1], transfer_route[i])];
            dis1 += sub_network.id2edge[eid].dist;
            if(sub_network.id2vertex[transfer_route[i]].isMiddle) continue;  // 中继卫星不能作为合并的终点
            if(dis1 < left_d && distance_sum-dis1 < left_d2){
                uint32_t tmp = dis1*s1 + (distance_sum-dis1)*s2;
                if(tmp < min_cost){
                    min_cost = tmp;
                    merged_vid = transfer_route[i];
                }
            }
        }

        if(merged_vid == UNDEFINED_NUMBER) return false;  // 不能找到一个合并顶点

        // 制作两个顶点的合并路线
        for(uint32_t i=0; ; ++i){
            transfer_route1.push_back(transfer_route[i]);
            if(transfer_route[i] == merged_vid) break;
        }
        for(uint32_t i=transfer_route.size()-1; ; --i){
            transfer_route2.push_back(transfer_route[i]);
            if(transfer_route[i] == merged_vid) break;
        }

        // 计算路径1和路径2的总路径花费
        uint32_t path_add_cost1 = 0, path_add_cost2 = 0;
        for(uint32_t i=1; i<transfer_route1.size(); ++i){
            uint32_t eid = sub_network.vertexs2edge[make_pair(transfer_route1[i-1], transfer_route1[i])];
            for(uint32_t sid : vertex.signals){
                path_add_cost1 += sub_network.id2edge[eid].dist*sub_network.id2signal[sid].power;
            }
        }
        for(uint32_t i=1; i<transfer_route2.size(); ++i){
            uint32_t eid = sub_network.vertexs2edge[make_pair(transfer_route2[i-1], transfer_route2[i])];
            for(uint32_t sid : vertex2.signals){
                path_add_cost2 += sub_network.id2edge[eid].dist*sub_network.id2signal[sid].power;
            }
        }

        // 计算总共节省的花费
        lowered_cost = gPS - (path_add_cost1+path_add_cost2)*gC;
        if(lowered_cost > 0) return true;  // 路径增加的花费小于减少的接收卫星的花费时，寻路成功
    }
    return false;
}

bool dfs2(uint32_t nid, uint32_t curr, uint32_t curr_distance, uint32_t& min_distance, uint32_t vid1_leftd,
          vector<bool> visited, vector<uint32_t> route_curr, vector<uint32_t>& route_record){
    if(visited[curr] || curr_distance >  min_distance) return false;

    visited[curr] = true;  // 标记顶点已遍历

    auto& sub_network = networks[nid];
    auto& vertex = sub_network.id2vertex[curr];
    if(!vertex.signals.empty() && curr_distance > 0){   // 找到邻近的有信号顶点
        // 判断是否源顶点的信号和目的顶点的信号的剩余距离是否可以走完路径
        uint32_t curr_leftd = vertex_left_dist(nid, curr);
        if(vid1_leftd + curr_leftd >= curr_distance){
            min_distance = curr_distance;
            route_record = route_curr;
            return true;
        }else{
            return false;
        }
    }

    bool f = false;
    for(uint32_t vid:vertex.neighbors){
        // 信号不能再回发射基站
        if(!id2type[vid]) continue;
        // 信号找新的路时不能经过已经确定是中继卫星的顶点
        uint32_t eid = sub_network.vertexs2edge[make_pair(curr, vid)];
        auto& edge = sub_network.id2edge[eid];
        // 路径长度限制
        if(curr_distance + edge.dist > min_distance) continue;
        // 路径重合约束，因为本方法合并在第三方空白点，所以不能走已经被染色的路
        if(edge.color != UNDEFINED_NUMBER) continue;

        route_curr.push_back(vid);  // 做出选择
        f |= dfs2(nid, vid, curr_distance + edge.dist, min_distance, vid1_leftd, visited, route_curr, route_record);
        route_curr.pop_back();  // 撤销选择
    }
    return f;
}


/* 合并信号3
 * 结合前两个策略，每次考虑两个策略结果，选取节省费用更多的那个进行执行
 * */
void merge_signals3(uint32_t nid){
    auto& sub_network = networks[nid];

    // 取出有信号的顶点，按照信号剩余最短距离排序
    vector<uint32_t> id_dis = vid_has_signals(nid);

    for(uint32_t vid:id_dis){
        auto& vertex = sub_network.id2vertex[vid];
        if(vertex.signals.empty()) continue;    // 顶点上无信号则跳过

        // method 1 寻找可行的转移路径
        vector<uint32_t> transfer_route;
        uint32_t lowered_cost1;
        bool f1 = find_a_route1(nid, vid, transfer_route, lowered_cost1);
        // method 2 寻找可行的转移路径
        uint32_t vid2 = UNDEFINED_NUMBER;
        vector<uint32_t> transfer_route1, transfer_route2;
        uint32_t lowered_cost2;
        bool f2 = find_a_route2(nid, vid, vid2, transfer_route1, transfer_route2, lowered_cost2);

        // 进行信号转移
        if(f1 && (!f2 || lowered_cost1>lowered_cost2)){  // 按方法1进行转移
            transfer_signals(nid, vid, transfer_route.back(), transfer_route);
        }else if(f2){  // 按方法2进行转移
            transfer_signals(nid, vid, transfer_route1.back(), transfer_route1);
            transfer_signals(nid, vid2, transfer_route2.back(), transfer_route2);
        }
    }
}


/* 合并信号，去选择一个最多信号可达的公共顶点，将信号迁移过去
 * 1. 对每个顶点进行dfs遍历，对遍历的顶点进行染色
 * 2. 选取颜色最深的顶点即最多的信号可以抵达的顶点
 * 3. 对每个信号进行找路并迁移，从当前顶点到颜色最新的顶点
 *
 * 欧洲杯之夜——我站意大利赢西班牙
 * */
void merge_signals_euro_cup(uint32_t nid){
    auto& sub_network = networks[nid];
    uint32_t cnt = sub_network.signals.size() - 1;  // 最多合并次数

    uint32_t hhh = 0;
    while(cnt--){

        clock_t end_time = clock();
        if((end_time - begin_time)/CLOCKS_PER_SEC > EXIT_TIME) break;

        vector<uint32_t> id_dis = vid_has_signals(nid);  // 有信号的顶点集合

        // 1. 染色
        vector<uint32_t> vertex_color(gN, 0);
        for(uint32_t vid:id_dis){
            uint32_t left_d = vertex_left_dist(nid, vid);
            vector<bool> visited(gN, false);
            paint_vertexs_euro_cup(nid, vid, left_d, visited, vertex_color);
        }

        end_time = clock();
        if((end_time - begin_time)/CLOCKS_PER_SEC > EXIT_TIME) break;

        // 2. 选取最深颜色的顶点
        uint32_t darkest_vertex = UNDEFINED_NUMBER, darkest_value = 1;
        for(uint32_t i=0; i<gN; ++i){
            if(vertex_color[i] > darkest_value){
                darkest_value = vertex_color[i];
                darkest_vertex = i;
            }
        }
        if(darkest_vertex == UNDEFINED_NUMBER) break;  // 没有找到可合并的节点则退出


        end_time = clock();
        if((end_time - begin_time)/CLOCKS_PER_SEC > EXIT_TIME) break;

        // 3. 找路
        uint32_t path_cost = 0;  // 路径增加的花费
        uint32_t decrese_number = 0;  // 减少的卫星数量
        for(uint32_t vid:id_dis){
            end_time = clock();
            if((end_time - begin_time)/CLOCKS_PER_SEC > EXIT_TIME) break;

            if(vid == darkest_vertex || sub_network.id2vertex[vid].signals.empty()) continue;
            uint32_t min_distance = vertex_left_dist(nid, vid);
            vector<bool> visited(gN, false);
            vector<uint32_t> route_curr, transfer_route;
            route_curr.push_back(vid);
            bool f = dfs_euro_cup(nid, vid, darkest_vertex, UNDEFINED_NUMBER, 0, min_distance, visited, route_curr, transfer_route);
            if(f){
                transfer_signals(nid, vid, darkest_vertex, transfer_route);
                // 计算路途费用
                for(uint32_t i=1; i<transfer_route.size(); ++i){
                    uint32_t eid = sub_network.vertexs2edge[make_pair(transfer_route[i-1], transfer_route[i])];
                    for(uint32_t sid : sub_network.id2vertex[vid].signals){
                        path_cost += sub_network.id2edge[eid].dist*sub_network.id2signal[sid].power;
                    }
                }
                decrese_number++;
            }
        }
        // 合并的代价高了则退出
        if(path_cost*gC > decrese_number*gPS){
            if(hhh > 3) break;
            else hhh++;
        }
    }
}

/* 从当前节点开始对可以到达的节点进行染色
 * */
void paint_vertexs_euro_cup(uint32_t nid, uint32_t vid, uint32_t left_distance, vector<bool>& visited, vector<uint32_t>& vertex_color){
    auto& sub_network = networks[nid];
    auto& vertex = sub_network.id2vertex[vid];

    visited[vid] = true;     // 标记已遍历
    vertex_color[vid] += (11-gpower[vid]);  // 染色

    for(uint32_t neighbor_id : vertex.neighbors){
        if(!id2type[neighbor_id] || visited[neighbor_id]) continue;  // 跳过发射基站和已遍历过的节点
        auto& neighbor = sub_network.id2vertex[neighbor_id];
        if(neighbor.isMiddle) continue;  // 跳过中继卫星
        uint32_t eid = sub_network.vertexs2edge[make_pair(vid, neighbor_id)];
        uint32_t e_dis = sub_network.id2edge[eid].dist;
        if(e_dis > left_distance) continue;  // 距离不可达

        paint_vertexs_euro_cup(nid, neighbor_id, left_distance - e_dis, visited, vertex_color);
    }
}

/* 找出从curr到target的一条可行路线
 * */
bool dfs_euro_cup(uint32_t nid, uint32_t curr, uint32_t target, uint32_t color, uint32_t curr_distance, uint32_t& min_distance,
                  vector<bool> visited, vector<uint32_t> route_curr, vector<uint32_t>& route_record){
    clock_t end_time = clock();
    if((end_time - begin_time)/CLOCKS_PER_SEC > EXIT_TIME) return false;


    if(visited[curr] || curr_distance >  min_distance) return false;
    visited[curr] = true;  // 标记顶点已遍历

    if(curr == target){  // 找到路径
        min_distance = curr_distance;
        route_record = route_curr;
        return true;
    }

    bool f = false;
    auto& sub_network = networks[nid];
    auto& vertex = sub_network.id2vertex[curr];
    for(uint32_t vid:vertex.neighbors){
        if(!id2type[vid]) continue;  // 信号不能再回发射基站
        uint32_t eid = sub_network.vertexs2edge[make_pair(curr, vid)];
        auto& edge = sub_network.id2edge[eid];
        // 路径长度限制
        if(curr_distance + edge.dist > min_distance) continue;
        // 路径重合约束
        if(color != UNDEFINED_NUMBER && color != edge.color) continue;
        else if(color == UNDEFINED_NUMBER) color = edge.color;

        // 如果经过非空顶点，判断当前非空节点的信号是否能迁往target
        if(!sub_network.id2vertex[vid].signals.empty()){
            end_time = clock();
            if((end_time - begin_time)/CLOCKS_PER_SEC > EXIT_TIME) return false;


            uint32_t min_distance2 = vertex_left_dist(nid, vid);
            vector<bool> visited2(gN, false);
            for(uint32_t i=0; i<gN; ++i){  // 已遍历过的有信号的顶点标记true，避免无穷递归
                if(visited[i] && !sub_network.id2vertex[i].signals.empty()){
                    visited2[i] = true;
                }
            }
            vector<uint32_t> route_curr2, transfer_route2;
            route_curr2.push_back(vid);
            if(dfs_euro_cup(nid, vid, target, 0, 0, min_distance2, visited2, route_curr2, transfer_route2)){
                transfer_signals(nid, vid, target, transfer_route2);
            }else{
                continue;
            }
        }

        route_curr.push_back(vid);  // 做出选择
        f |= dfs_euro_cup(nid, vid, target, color, curr_distance + edge.dist, min_distance, visited, route_curr, route_record);
        route_curr.pop_back();  // 撤销选择
    }
    return f;
}


class Solution {
public:
    vector<Route> Plan(uint32_t N, uint32_t C, uint32_t D, uint32_t PS,
                       const vector<bool>& typeVec, const vector<int>& power,
                       const vector<Edge>& edgeVec)
    {
        // 解析数据
        parse_data(N, C, D, PS, typeVec, power, edgeVec);
        // 划分子网
        divide_network(edgeVec);

        // 对每一个子网做规划
        for(uint32_t i = 0; i<networks.size(); ++i){
            basic_route(i);     // 得到基础的可行解
//            merge_signals1(i);  // 合并策略1
//            merge_signals2(i);  // 合并策略2
//            merge_signals3(i);  // 合并策略3

            merge_signals_euro_cup(i);  // 欧洲杯之夜的合并策略
//            merge_signals3(i);  // 合并策略3
        }

        // 返回结果
        vector<Route> retRouteVec;
        for(auto& sub_network : networks){
            for(uint32_t sid:sub_network.signals){
                // 对路径进行一个优化，去掉重复路径
                vector<uint32_t> src_route = sub_network.id2signal[sid].route;
                uint32_t route_len = src_route.size();
                for(uint32_t i=0; i<route_len; ++i){
                    if(src_route[i] == UNDEFINED_NUMBER) continue;
                    for(uint32_t j=route_len-1; j>i; --j){
                        if(src_route[i] == src_route[j]){
                            for(uint32_t k = i+1; k<=j; ++k) src_route[k] = UNDEFINED_NUMBER;
                            break;
                        }
                    }
                }
                vector<uint32_t> better_route;
                for(uint32_t i:src_route){
                    if(i != UNDEFINED_NUMBER) better_route.push_back(i);
                }
                // 加入输出
                retRouteVec.push_back(better_route);
            }
        }
        return retRouteVec;
    }
};


int main(int argc, char *argv[])
{
    begin_time = clock();
#ifdef DEBUG
    //    freopen("../../judge/cases/Example.case", "r", stdin);
    freopen("../../judge/cases/TestData_24.case", "r", stdin);
#endif
    uint32_t N;             // 表示所有卫星和发射基站的总数
    uint32_t E;             // 表示网络中可使用的路径总数
    uint32_t C;             // 表示路径距离L与功耗P的系数，传输功耗计算公式为：P=C*L
    uint32_t D;             // 表示全网最大路径长度限制。
    uint32_t PS;            // 表示接收卫星所需要的站点功耗
    vector<bool> typeVec;   // 下标为i的值代表ID为i的站点身份，卫星为true，发射基站为false
    vector<int> power;      // 顶点的功耗
    vector<Edge> edgeVec;   // 包含E条边

    cin >> N >> E >> C >> D >> PS;
    typeVec = vector<bool>(N);
    for (uint32_t i = 0; i < N; i++) {
        bool type;
        cin >> type;
        typeVec[i] = type;
    }
    power = vector<int>(N);
    for (uint32_t i = 0; i < N; i++) {
        int p;
        cin >> p;
        power[i] = p;
    }
    edgeVec = vector<Edge>(E);
    for (auto& edge : edgeVec) {
        cin >> edge.send >> edge.recv >> edge.dist;
    }

    Solution solution;
    vector<Route> retRouteVec = solution.Plan(N, C, D, PS, typeVec, power, edgeVec);
    for (const auto& route : retRouteVec) {
        for (const auto& siteId : route) {
            cout << siteId << " ";
        }
        cout << "\n";
    }
    return 0;
}
